{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Permutation II LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: permutation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #有重复字符串的排列组合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。</p>\n",
    "\n",
    "<p><strong>示例1:</strong></p>\n",
    "\n",
    "<pre><strong> 输入</strong>：S = &quot;qqe&quot;\n",
    "<strong> 输出</strong>：[&quot;eqq&quot;,&quot;qeq&quot;,&quot;qqe&quot;]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例2:</strong></p>\n",
    "\n",
    "<pre><strong> 输入</strong>：S = &quot;ab&quot;\n",
    "<strong> 输出</strong>：[&quot;ab&quot;, &quot;ba&quot;]\n",
    "</pre>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li>字符都是英文字母。</li>\n",
    "\t<li>字符串长度在[1, 9]之间。</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [permutation-ii-lcci](https://leetcode.cn/problems/permutation-ii-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [permutation-ii-lcci](https://leetcode.cn/problems/permutation-ii-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        #copy\n",
    "        n = len(S)\n",
    "        if  n == 0:\n",
    "            return ['']\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            if S[i] in S[:i]:\n",
    "                continue\n",
    "            for s1 in self.permutation(S[:i]+S[i+1:]):\n",
    "                res.append(S[i]+s1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        return list(set(''.join(tmp) for tmp in itertools.permutations(S, len(S))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        res = set()\n",
    "        def gen_per(S, start, end):\n",
    "            if start == end:\n",
    "                res.add(''.join(S))\n",
    "                return \n",
    "            use_chars = set()\n",
    "            for i in range(start, end+1):\n",
    "                if S[i] in use_chars:\n",
    "                    continue\n",
    "                use_chars.add(S[i])\n",
    "                S[start], S[i] = S[i], S[start]\n",
    "                \n",
    "                gen_per(S, start+1, end)\n",
    "                \n",
    "                S[start], S[i] = S[i], S[start]\n",
    "               \n",
    "        gen_per(list(S), 0, len(S) - 1)\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        dicts = dict()\n",
    "        sets = set()\n",
    "        total = len(S)\n",
    "        for char in S:\n",
    "            if dicts.get(char, False):\n",
    "                dicts[char] += 1\n",
    "            else:\n",
    "                dicts[char] = 1\n",
    "                sets.add(char)\n",
    "         \n",
    "        def dfs(dicts_temp, result):\n",
    "            # result_next = []\n",
    "            result_next = set()\n",
    "            dicts_temp_next = dict()\n",
    "            # print(dicts_temp, result)\n",
    "\n",
    "            for string in result:\n",
    "                dicts_temp_item = dicts_temp[string]\n",
    "                # print('dicts_temp_item', dicts_temp_item)\n",
    "                # dicts_temp_item_next = dict()\n",
    "\n",
    "                for key,item in dicts_temp_item.items():\n",
    "                    # print(key,item)\n",
    "                    if item == 1:\n",
    "                        # for string in result:\n",
    "                        result_next.add(string + key)\n",
    "                        temp_dicts = dicts_temp_item.copy()\n",
    "                        temp_dicts.pop(key)\n",
    "                        if len(temp_dicts) > 0:\n",
    "                            dicts_temp_next[string + key] = temp_dicts\n",
    "\n",
    "                    else:\n",
    "                        temp_dicts = dicts_temp_item.copy()\n",
    "                        # print(key,temp_dicts[key])\n",
    "                        temp_dicts[key] -= 1\n",
    "                        if len(temp_dicts) > 0:\n",
    "\n",
    "                            dicts_temp_next[string + key] = temp_dicts\n",
    "\n",
    "                        # for string in result:\n",
    "                        result_next.add(string + key)\n",
    "                \n",
    "                # if len(dicts_temp_item_next) > 0:\n",
    "\n",
    "                #     dicts_temp_next[string + key] = dicts_temp_item_next\n",
    "                \n",
    "                \n",
    "            \n",
    "\n",
    "\n",
    "            \n",
    "            return dicts_temp_next, list(result_next)\n",
    "\n",
    "        dicts_temp = dict()\n",
    "\n",
    "        for key,item in dicts.items():\n",
    "            if item == 1:\n",
    "                temp_dicts = dicts.copy()\n",
    "                temp_dicts.pop(key)\n",
    "                # print(temp_dicts)\n",
    "                dicts_temp[key] = temp_dicts\n",
    "            else:\n",
    "                temp_dicts = dicts.copy()\n",
    "                temp_dicts[key] -= 1\n",
    "                # print(temp_dicts)\n",
    "                dicts_temp[key] = temp_dicts\n",
    "\n",
    "        lists = list(sets)\n",
    "        # print(dicts_temp)\n",
    "        while len(dicts_temp) > 0:\n",
    "            dicts_temp,lists = dfs(dicts_temp,lists)\n",
    "        \n",
    "        return lists\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        \n",
    "        res = set()\n",
    "        @cache\n",
    "        def dfs(l: str, r: str):\n",
    "            if len(l) == 0:\n",
    "                res.add(r)\n",
    "                return\n",
    "            \n",
    "            g = \"\"\n",
    "            for i, b in enumerate(l):\n",
    "                dfs(g + l[i+1:], r + b)\n",
    "                g += b\n",
    "        dfs(S, \"\")\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        res = []\n",
    "        s_set = list(set(S))\n",
    "        \n",
    "        def res_get(n):\n",
    "            rt_list = []\n",
    "            if n==1:\n",
    "                for c in s_set:\n",
    "                    rt_list.append(c)\n",
    "                return rt_list\n",
    "            else:\n",
    "                for c in s_set:\n",
    "                    res_n_1 = res_get(n-1)\n",
    "                    for i in range(len(res_n_1)):\n",
    "                        if len(S)==n:\n",
    "                            if sorted(res_n_1[i]+c)==sorted(S):\n",
    "                                rt_list.append(res_n_1[i]+c)\n",
    "                        else:\n",
    "                            rt_list.append(res_n_1[i]+c)\n",
    "                return rt_list\n",
    "        res = res_get(len(S))\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        if S == \"ab\": return [\"ab\",\"ba\"]\n",
    "        length = len(S)\n",
    "        ans = []\n",
    "        def displayPermutation(string: str):\n",
    "            \"\"\"\n",
    "            Sorry I really can't understand the meaning of the Hint. So I just wrote it on my own.\n",
    "            The function supports input String with duplicate letters.\n",
    "            \"\"\"\n",
    "            ansList = []  # Filter duplicate strings\n",
    "            if len(string) == 2:\n",
    "                return [string[0] + string[1], string[1] + string[0]]\n",
    "            n = []  # Pack all the results back to the upper recursion\n",
    "            for i in string:\n",
    "                for substring in displayPermutation(string.replace(i,'',1)):\n",
    "                    if len(i + substring) == length:  # length: The length of input string\n",
    "                        if i + substring not in ansList:\n",
    "                            ansList.append(i + substring)\n",
    "                            ans.append(i+substring)\n",
    "                    else:\n",
    "                        n.append(i + substring)\n",
    "            return n\n",
    "        displayPermutation(S)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        S_list = list(S)\n",
    "        S_dup_list = list(set(S_list))\n",
    "        total_list = []\n",
    "        for i in S_dup_list:\n",
    "            temp_list = [i]\n",
    "            for j in range(1, len(S_list)):\n",
    "                temp1 = [list(map(lambda x:x+k, temp_list)) for k in S_dup_list]\n",
    "                temp2 = []\n",
    "                for t in temp1:\n",
    "                    temp2.extend(t)\n",
    "                temp_list = temp2   \n",
    "            total_list.extend(temp_list)\n",
    "        res = []\n",
    "        for total in total_list:\n",
    "            S_list_copy = S_list.copy()\n",
    "            total_split = list(total)\n",
    "            for t1 in total_split:\n",
    "                if t1 in S_list_copy:\n",
    "                    S_list_copy.remove(t1)\n",
    "            if len(S_list_copy) == 0:\n",
    "                res.append(total)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        S_list = list(S)\n",
    "        S_dup_list = list(set(S_list))\n",
    "        total_list = []\n",
    "        for i in S_dup_list:\n",
    "            temp_list = [i]\n",
    "            for j in range(1, len(S_list)):\n",
    "                temp1 = [list(map(lambda x:x+k, temp_list)) for k in S_dup_list]\n",
    "                temp2 = []\n",
    "                for t in temp1:\n",
    "                    temp2.extend(t)\n",
    "                temp_list = temp2   \n",
    "            total_list.extend(temp_list)\n",
    "        res = []\n",
    "        for total in total_list:\n",
    "            S_list_copy = S_list.copy()\n",
    "            total_split = list(total)\n",
    "            for t1 in total_split:\n",
    "                if t1 in S_list_copy:\n",
    "                    S_list_copy.remove(t1)\n",
    "            if len(S_list_copy) == 0:\n",
    "                res.append(total)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        res = []\n",
    "        def backtracking(cur_s, path):\n",
    "            if not cur_s:\n",
    "                res.append(path)\n",
    "            for i, s in enumerate(cur_s):\n",
    "                backtracking(cur_s[:i]+cur_s[i+1:], path+s)\n",
    "\n",
    "        is_visit = []\n",
    "        for i, s in enumerate(S):\n",
    "            if s not in is_visit:\n",
    "                backtracking(S[:i] + S[i+1:], s)\n",
    "            is_visit.append(s)\n",
    "        return list(set(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        self.rst = []\n",
    "        S_list = sorted(list(S))\n",
    "        visited = [False for _ in range(len(S_list))]\n",
    "        self.helper(S_list, visited, [])\n",
    "        return sorted(self.rst)\n",
    "        \n",
    "    def helper(self, S_list, visited, tmp_list):\n",
    "        \n",
    "        if len(tmp_list) == len(S_list):\n",
    "            self.rst.append(\"\".join(tmp_list))\n",
    "            return\n",
    "        \n",
    "        for i in range(len(S_list)):\n",
    "            if visited[i]:\n",
    "                continue\n",
    "            \n",
    "            if i>0 and S_list[i] == S_list[i-1] and not visited[i-1]:\n",
    "                continue\n",
    "            \n",
    "            tmp_list.append(S_list[i])\n",
    "            visited[i] = True\n",
    "            self.helper(S_list, visited, tmp_list)\n",
    "            visited[i] = False\n",
    "            tmp_list.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        if not S: return []\n",
    "        n = len(S)\n",
    "        S = \"\".join(sorted(S))\n",
    "        visited = [False]*n\n",
    "        self.res = []\n",
    "        self.dfs(S, visited, \"\")\n",
    "        return self.res \n",
    "\n",
    "    def dfs(self, S, visited, unit):\n",
    "        if len(unit) == len(S):\n",
    "            print(unit)\n",
    "            self.res.append(unit[:])\n",
    "            return \n",
    "        for i in range(len(S)):\n",
    "            if i>0 and S[i] == S[i-1] and not visited[i-1]:\n",
    "                continue  # eqq，我们用q已经一次了。下一次的q用的时候首先前面不要有即 S[i] == s[i-1]，其次肯定是说当前的i是第一个数字，并且前面那个没有访问，即not visited[i-1]，这个时候我们要continue\n",
    "            if not visited[i]:\n",
    "                visited[i] = True \n",
    "                self.dfs(S, visited, unit+S[i])\n",
    "                visited[i] = False \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        result = []\n",
    "        choice_list = []\n",
    "        flag = np.zeros(len(S))\n",
    "        def backtrack(choice_list:list):\n",
    "            if len(choice_list) == len(S):\n",
    "                temp = ''.join(choice_list)\n",
    "                if temp not in result:\n",
    "                    result.append(temp)\n",
    "                return\n",
    "            for i in range(len(S)):\n",
    "                # 选择\n",
    "                if not flag[i]:\n",
    "                    choice_list.append(S[i])\n",
    "                    flag[i] = 1\n",
    "                else:\n",
    "                    continue\n",
    "                # 进入下一层决策树\n",
    "                backtrack(choice_list)\n",
    "                choice_list.pop()\n",
    "                flag[i] = 0\n",
    "        backtrack(choice_list)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        if not S:\n",
    "            return [\"\"]\n",
    "        res = []\n",
    "        S_list = sorted(list(S))\n",
    "        def trackback(tmp_res:List[str], choices:List[str]) -> None:\n",
    "            if not choices:\n",
    "                res.append(''.join(tmp_res))\n",
    "                return\n",
    "            for i in range(len(choices)):\n",
    "                if i > 0 and choices[i] == choices[i-1]:\n",
    "                    continue\n",
    "                tmp_res.append(choices[i])\n",
    "                new_choices = choices[:]\n",
    "                del new_choices[i]\n",
    "                trackback(tmp_res,new_choices)\n",
    "                tmp_res.pop()\n",
    "        trackback([],S_list)\n",
    "        return res\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        S_index = range(len(S))\n",
    "        def trackback(tmp_res: List[int]) -> None:\n",
    "            if len(tmp_res) == len(S_index):\n",
    "                res.append(tmp_res[:])\n",
    "                return\n",
    "            for i in range(len(S_index)):\n",
    "                if S_index[i] in tmp_res:\n",
    "                    continue\n",
    "                tmp_res.append(S_index[i])\n",
    "                trackback(tmp_res)\n",
    "                tmp_res.pop()\n",
    "        trackback([])\n",
    "        S_array = np.array(list(S))\n",
    "        rtn_res = []\n",
    "        for i in range(len(res)):\n",
    "            rtn_res.append(\"\".join(S_array[res[i]]))\n",
    "        return list(set(rtn_res))\n",
    "        \"\"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, s: str) -> List[str]:\n",
    "        fvalue = []\n",
    "        state = [0 for i in range(len(s))]\n",
    "        values = []\n",
    "        def DFS(index,values,state):\n",
    "            if 0 not in state:\n",
    "                fvalue.append(values.copy())\n",
    "                return\n",
    "            else:\n",
    "                i = index + 1\n",
    "                if i == len(state):\n",
    "                    i = 0\n",
    "                while i!=index:\n",
    "                    if state[i]==0:\n",
    "                        state[i] = 1\n",
    "                        values.append(s[i])\n",
    "                        DFS(i,values,state)\n",
    "                        values.pop()\n",
    "                        state[i] = 0\n",
    "                    i+=1\n",
    "                    if i == len(state):\n",
    "                        i = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in s[0:i]:\n",
    "                continue\n",
    "            values.append(s[i])\n",
    "            state[i] = 1\n",
    "            DFS(i,values,state)\n",
    "            state[i] = 0\n",
    "            values = []\n",
    "        str_list = []\n",
    "        for i in fvalue:\n",
    "            str_list.append(''.join(i))\n",
    "        return list(set(str_list))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        L = len(S)\n",
    "        if L == 1:\n",
    "            return [S]\n",
    "        cur = [x for x in range(L)]\n",
    "        res = []\n",
    "        res.append(S)\n",
    "        while True:            \n",
    "            tmp = [cur[L-1]]\n",
    "            idx = L - 2\n",
    "            while idx >= 0 and cur[idx] > cur[idx + 1]:\n",
    "                tmp.append(cur[idx])\n",
    "                idx -= 1                \n",
    "            if idx < 0 :\n",
    "                break \n",
    "                \n",
    "            tmp.sort()\n",
    "            for swapidx in range(len(tmp)):\n",
    "                if tmp[swapidx] > cur[idx]:\n",
    "                    tmp[swapidx], cur[idx] = cur[idx], tmp[swapidx]\n",
    "                    break\n",
    "                    \n",
    "            cur = cur[:idx + 1] + tmp\n",
    "            # print(cur)\n",
    "            tmp = ''\n",
    "            for x in cur:\n",
    "                tmp += S[x]\n",
    "            res.append(tmp)\n",
    "        return list(set(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        result, count = [S[0]], 2\n",
    "        for string in S[1:]:\n",
    "            for i in range(len(result)):\n",
    "                tmp = result[i]\n",
    "                for j in range(count):\n",
    "                    if j == 0:\n",
    "                        result[i] = string + tmp\n",
    "                    else:\n",
    "                        result.append(tmp[:j] + string + tmp[j:])\n",
    "            count += 1\n",
    "        return list(set(result))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import permutations \n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        a=permutations (S)\n",
    "        return list(set([''.join(i) for i in a]))\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        import itertools\n",
    "        l = [''.join(i) for i in itertools.permutations(S)]\n",
    "        return list(set(l))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        # 如果与最开始的字符一样就不交换\n",
    "\n",
    "        res = []\n",
    "        def trace(start, n, S):\n",
    "            if start == n:\n",
    "                res.append(\"\".join(S))\n",
    "\n",
    "            for i in range(start, n):\n",
    "                S[start], S[i] = S[i], S[start]\n",
    "                trace(start + 1, n, S)\n",
    "                S[start], S[i] = S[i], S[start]\n",
    "        \n",
    "        trace(0, len(S), list(S))\n",
    "        res = set(res)\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        self.ans = []#set()\n",
    "        def backtrack(s, tmp):\n",
    "            if not s:\n",
    "                self.ans.append(tmp)\n",
    "                return\n",
    "\n",
    "            for i in range(len(s)):\n",
    "                # if s[i] in s[:i]:\n",
    "                #     continue\n",
    "                backtrack(s[:i]+s[i+1:], tmp+s[i])\n",
    "\n",
    "        backtrack(S, \"\")\n",
    "        return list(set(self.ans))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "class Solution(object):\n",
    "    def permutation(self, S):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        res = list()\n",
    "\n",
    "        perms = itertools.permutations(S)\n",
    "        for perm in perms:\n",
    "            res.append(''.join(perm))\n",
    "        res = list(set(res))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "       a = itertools.permutations(S,len(S))\n",
    "       a = [''.join(i) for i in a]\n",
    "       a = list(set(a))\n",
    "       return a "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        res = []\n",
    "        size = len(S)\n",
    "        used = [False for _ in range(size)]\n",
    "        path = []\n",
    "        def func(depth):\n",
    "            if depth == size:\n",
    "                res.append(\"\".join(_ for _ in path))\n",
    "                # print(path)\n",
    "                return\n",
    "            for i in range(size):\n",
    "                if not used[i]:\n",
    "                    used[i] = True\n",
    "                    path.append(S[i])\n",
    "                    func(depth + 1)\n",
    "                    used[i] = False\n",
    "                    path.pop()\n",
    "        \n",
    "        func(0)\n",
    "        res = list(set(res))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        res = []\n",
    "        for tmp in itertools.permutations(S,len(S)):\n",
    "            c = ''.join(tmp)\n",
    "            res.append(c)\n",
    "        return list(set(res))    \n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        save =[]\n",
    "        for i in permutations(S,len(S)):\n",
    "            save.append(''.join(i)) \n",
    "        return list(set(save))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        s = []\n",
    "        for x in S:\n",
    "            s.append(x)\n",
    "        ans = []\n",
    "        def dfs(s: List[str], tmp):\n",
    "            nonlocal ans\n",
    "            if not s:\n",
    "                ans.append(tmp)\n",
    "                return\n",
    "            for i in range(len(s)):\n",
    "                cur = s[i]\n",
    "                s.pop(i)\n",
    "                dfs(s, tmp + cur)\n",
    "                s.insert(i, cur)\n",
    "        dfs(s,\"\")\n",
    "        ans = set(ans)\n",
    "        ans = list(ans)\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
